
public class Test3 {
    public static void main(String[] args) {
        printPrimesUpTo20000();
    }

    /**
     * 使用埃氏筛法打印1~20000之间的所有素数，每行5个
     */
    private static void printPrimesUpTo20000() {
        int max = 20000;
        // 布尔数组标记是否为合数（非素数），默认false（素数）
        boolean[] isComposite = new boolean[max + 1];
        int primeCount = 0;

        // 0和1不是素数，可直接标记，但本程序不处理它们的打印
        // 从2开始筛选，标记所有非素数
        for (int i = 2; i * i <= max; i++) {
            // 如果当前数是素数，则标记其所有倍数为非素数
            if (!isComposite[i]) {
                // 从i*i开始标记（优化点：小于i*i的倍数已被更小的数标记过）
                for (int j = i * i; j <= max; j += i) {
                    isComposite[j] = true;
                }
            }
        }

        // 遍历数组，打印所有未被标记为合数的数（即素数）
        for (int num = 2; num <= max; num++) {
            if (!isComposite[num]) {
                // 格式化输出，每个数字占6个字符宽度，左对齐
                System.out.printf("%-6d", num);
                primeCount++;
                // 每5个素数换行
                if (primeCount % 5 == 0) {
                    System.out.println();
                }
            }
        }
    }
}
